package com.zz.query;

/**
 * @author 张哲
 * @email a252013135@163.com
 * @date 2024/7/25 8:47
 * <p>
 * 某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席，请返回他的学号。
 * 示例 1:
 * 输入: records = [0,1,2,3,5]
 * 输出: 4
 * <p>
 * 示例 2:
 * 输入: records = [0, 1, 2, 3, 4, 5, 6, 8]
 * 输出: 7
 * <p>
 * 提示：
 * 1 <= records.length <= 10000
 */
public class LCR173Solution {
    /**
     * 暴力
     *
     * @param records
     * @return
     */
    public int takeAttendance1(int[] records) {
        for (int i = 0; i < records.length; i++) {
            if (i != records[i]) {
                return i;
            }
        }
        return records.length;
    }

    /**
     * 二分法
     *
     * @param records
     * @return
     */
    public int takeAttendance(int[] records) {
        int left = 0, right = records.length;
        //区间为：左闭右开

        while(left < right) {
            int m = left + (right - left) / 2;

            if(records[m] == m)
                left = m + 1;
            else
                right = m;
        }
        return left;
    }
}
